package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/8/12 22:41
 */
public class LowesetCostClimbingStairs_746 {

    public int minCostClimbingStairs(int[] cost) {
        final int[] dp = new int[cost.length + 1];
        // 不需要支付任何代价就可以上一层或者2层
        // 要跨过第2层需要支付cost[0]和cost[1]中的较小值
        // 可以选择先到1，然后跨过2
        // 或者直接到3
        dp[2] = Math.min(cost[0], cost[1]);
        for (int i = 3; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }
        return dp[cost.length];

    }

    public int betterAnswer(int[] cost) {
        int f0 = 0, f1 = 0;
        for (int value : cost) {
            int cur = value + Math.min(f0, f1);
            f0 = f1;
            f1 = cur;
        }
        return Math.min(f0, f1);
    }
}
